home *** CD-ROM | disk | FTP | other *** search
/ Scene Storm / Scene Storm - Volume 1.iso / coding / asm / misc / quicksort / qsort.s next >
Text File  |  1980-01-03  |  2KB  |  61 lines
  1. ***********************************************************
  2. * Quick Sort
  3. ***********************************************************
  4. * Sorts a random array of integers in N*log(N) time.
  5. *
  6. * Input:
  7. * 4(sp) : ptr to first element
  8. * 8(sp) : ptr to last element
  9. *
  10. * Output:
  11. * none
  12. *
  13. * Uses:
  14. * d0 : "partition" element.
  15. * d1 : temporary used to exchange elements.
  16. * a0 : first element in array.
  17. * a1 : last element in array.
  18. * a2 : scanning pointer
  19. * a3 : scanning pointer
  20. ***********************************************************
  21.  
  22. first        EQU    4
  23. last        EQU    8
  24.  
  25. ExgM        MACRO    \1,\2
  26.         move.l    \1,d1        ; 12 cycles
  27.         move.l    \2,\1        ; 20 cycles
  28.         move.l    d1,\2        ; 12 cycles
  29.         ENDM
  30.  
  31. ***********************************************************
  32.  
  33. QuickSort:    move.l    first(sp),a0    ; first element
  34.         move.l    last(sp),a1    ; last element
  35.  
  36. .QSort:        cmp.l    a1,a0        ; are we done yet?
  37.         bgt.b    .done        ; yes. begin recursive return.
  38.  
  39.         move.l    (a1),d0        ; No.  Load the partition variable,
  40.         move.l    a0,a2        ;   the left side incrementing ptr,
  41.         move.l    a1,a3        ;   and the right side dec. ptr.
  42.  
  43. .loop1:        cmp.l    (a2)+,d0    ; <---+ Scan left ptr up for a swap
  44.         bgt.b    .loop1        ; >---+
  45.         subq.l    #4,a2        ;     | Get rid of last post inc.
  46. .loop2:        cmp.l    -(a3),d0    ; <-+ | scan right ptr dwn for a swap
  47.         blt.b    .loop2        ; >-+ |
  48.         cmp.l    a3,a2        ;     | Did the pointers cross?
  49.         bgt.b    .break        ; >-+ | Yes, break out of the loop
  50.         ExgM    (a2),(a3)    ;   | | Swap the out of place ele.
  51.         bra.b    .loop1        ; >-|-+
  52.                     ;   |
  53. .break:        ExgM    (a1),(a2)    ; <-+   Swap them.
  54.         move.l    a1,-(sp)    ; last element for 2nd recur.
  55.         pea    4(a2)        ; first element for 2nd recur.
  56.         lea    -4(a2),a1    ; last element for 1st recur.
  57.         bsr.b    .QSort        ; first recur.
  58.         bsr.b    QuickSort    ; second recur.
  59.         addq.l    #8,sp        ; restore stack
  60. .done:        rts            ; return to caller.
  61.